package leetcode.hot100;

public class Solution283 {

    public static void main(String[] args) {
        int[] nums = {3,1,5,3,12};
        new Solution283().moveZeroes(nums);
        System.out.println();
    }

    public void moveZeroes1(int[] nums) {
        //双指针，i指向未扫描过的第一个0,j指向i后第一个非0
        int nextNotZero = -1 ,len = nums.length;
        for (int i = 0; i < len; i++) {
            if(nums[i]==0){
                //寻找最近的非0
                if(nextNotZero==-1) nextNotZero = i+1; //i是第一个0初始化
                while (nextNotZero<len&&nums[nextNotZero]==0) nextNotZero++;
                //找不到下一个非0，全是0了，排好了
                if(nextNotZero>=len) return;
                //交换
                nums[i] = nums[nextNotZero];
                nums[nextNotZero] = 0;
                nextNotZero ++; //下一个非0移动
            }
        }
    }

    public void moveZeroes(int[] nums) {
        //left左边开始非0数字后面第一个0，right指向未处理的非0数字，二者之间都是0
        int left = 0, right = 0, len = nums.length;
        while (right<len){
            if(nums[right]!=0){
                int tmp = nums[left];
                nums[left] = nums[right];
                nums[right] = tmp;
                left++;
            }
            right++;
        }

    }

}
